package labuladong.动态规划;

public class 完全背包硬币兑换问题 {

    public static int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length+1][amount+1];
        for (int i=0; i<=coins.length; i++) {
            dp[i][0] = 1;
        }
        for (int i=1; i<=coins.length; i++) {
            for (int j=1; j<=amount; j++) {
                if (j-coins[i-1] >= 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                } else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[coins.length][amount];
    }

    public static void main(String[] args) {
        System.out.println(change(5, new int[]{1, 2, 5}));
    }
}
